﻿// 4224. 起火迷宫.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>




using namespace std;
/*
https://www.acwing.com/problem/content/4227/
一个迷宫可以看作一个 R行 C 列的方格矩阵。

其中一些方格是空地，用 . 表示，其他方格是障碍，用 # 表示。

开始时，乔位于一块空地之中。

迷宫中一些空地已经起火了，幸运的是火还没有蔓延至乔所在的位置。

为了避免被火烧伤，乔需要尽快逃离迷宫。

已知，乔每单位时间只能沿上下左右四个方向前进一格距离，并且在前进过程中，他不能进入障碍方格。

火每单位时间都会蔓延至其上下左右四个方向的相邻空地，但是火也会被障碍阻挡。

如果一个方格已经起火或者会在乔进入方格的那一时刻恰好起火，则该方格很危险，乔不能进入。

当乔进入到任意一个位于边界的空地方格时，他都可以再花费一单位时间，直接逃离迷宫。

请问，乔想要逃离迷宫，最少需要花费的时间。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 R,C。

接下来 R行，包含一个 R×C的字符矩阵。

矩阵中只包含以下四种字符：

# 表示障碍方格。
. 表示空地方格。
J 表示乔所在的空地方格，最多只有一个。
F 表示已经起火的空地方格。
输出格式
每组数据输出一行结果，一个整数表示逃离迷宫所需花费的最少时间，如果无法逃离迷宫，则输出 IMPOSSIBLE。

数据范围
1≤T≤10
,
1≤R,C≤1000
。

输入样例：
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
输出样例：
3
IMPOSSIBLE
*/

const int N = 1010;

char gra[N][N];

int fmap[N][N];

int vis[N][N];

int jmap[N][N];

int t, r, c;
int jx, jy;

int farr[N][2]; int fidx;

const int addx[] = { 1,-1,0,0 };
const int addy[] = { 0,0,1,-1 };

void markFire() {
	queue<pair<int, int>> q;
	for (int i = 0; i < fidx; i++) {
		int x = farr[i][0]; int y = farr[i][1];
		q.push({ x,y }); vis[x][y] = 1; fmap[x][y] = 0;
	}

	while (!q.empty()) {
		int x = q.front().first; int y = q.front().second;
		int step = fmap[x][y]; q.pop();

		for (int i = 0; i < 4; i++) {
			int newx = x + addx[i]; int newy = y + addy[i];
			if (newx >= 0 && newx < r && newy >= 0 && newy < c && vis[newx][newy] == 0 && gra[newx][newy] != '#') {
				q.push({ newx,newy });  vis[newx][newy] = 1; fmap[newx][newy] = step + 1;
			}
		}
	}
}

void bfs() {
	memset(vis, 0, sizeof vis);

	if (jx == 0 || jx == r - 1 || jy == 0 || jy == c - 1) {
		printf("1\n"); return;
	}

	queue<pair<int, int> > q;
	q.push({ jx,jy });  vis[jx][jy] = 1; jmap[jx][jy] = 0;

	while (!q.empty()) {
		int x = q.front().first; int y = q.front().second;
		int step = jmap[x][y]; q.pop();

		for (int i = 0; i < 4; i++) {
			int newx = x + addx[i]; int newy = y + addy[i];
			if (newx >= 0 && newx < r && newy >= 0 && newy < c && vis[newx][newy] == 0 && gra[newx][newy] != '#' && step+1 < fmap[newx][newy]) {
				//可以走该点
				if (newx == 0 || newx == r - 1 || newy == 0 || newy == c - 1) {
					printf("%d\n",step+2); return;
				}
				q.push({ newx,newy }); vis[newx][newy] = 1; jmap[newx][newy] = step + 1;
			}
		}
	}
 
	printf("IMPOSSIBLE\n"); return;
}

void solve() {
	markFire();
	bfs();
}

int main()
{
	scanf("%d",&t);
	while (t--) {
		fidx = 0;
		memset(fmap, 0x3f, sizeof fmap);
		memset(vis, 0, sizeof vis);
		memset(jmap, -1, sizeof jmap);

		scanf("%d%d", &r, &c);
		for (int i = 0; i < r; i++) {
			scanf("%s", gra[i]);
			for (int j = 0; j < c; j++) {
				if (gra[i][j] == 'F') { farr[fidx][0] = i; farr[fidx][1] = j; fidx++; }
				if (gra[i][j] == 'J') { jx = i; jy = j; }
			}
		}
		solve();
	}

	return 0;
}

 